package mashibing.class22;

/**
 * 给定3个参数，N，M，K
 * 怪兽有N滴血，等着英雄来砍自己
 * 英雄每一次打击，都会让怪兽流失[0~M]的血量
 * 到底流失多少？每一次在[0~M]上等概率的获得一个值
 * 求K次打击之后，英雄把怪兽砍死的概率
 */
public class Class22_1_KillMonster {

    public static double killMonster1(int N, int M, int K) {
        if (N < 1 || M < 1 || K < 1) {
            return 0;
        }
        long all = (long) Math.pow((M + 1), K);
        long process = process(K, M, N);
        return (double) process / (double) all;
    }

    public static long process(int k, int m, int hp) {
        if (k == 0) {
            return hp <= 0 ? 1 : 0;
        }
        if (hp <= 0) {
            return (long) Math.pow(m + 1, k);
        }
        long way = 0;
        for (int i = 0; i <= m; i++) {
            way += process(k - 1, m, hp - i);
        }
        return way;
    }

    public static double killMonster2(int n, int m, int k) {
        if (n < 1 || m < 1 || k < 1) {
            return 0;
        }
        long[][] dp = new long[k + 1][n + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= k; i++) {
            dp[i][0] = (long) Math.pow(m + 1, i - 1);
            for (int j = 1; j <= n; j++) {
                long way = 0;
                for (int l = 0; l <= m; l++) {
                    if (j - l > 0) {
                        way += dp[i - 1][j - l];
                    } else {
                        way += Math.pow(m + 1, i - 1);
                    }
                }
                dp[i][j] = way;
            }
        }
        return (double) dp[k][n] / Math.pow(m + 1, k);
    }

    public static double killMonster3(int n, int m, int k) {
        if (n < 1 || m < 1 || k < 1) {
            return 0;
        }
        long[][] dp = new long[k + 1][n + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= k; i++) {
            dp[i][0] = (long) Math.pow(m + 1, i);
            for (int j = 1; j <= n; j++) {
                long way = 0;

                way = dp[i][j - 1] + dp[i - 1][j];
                if(j - m > 0) {
                    way -= dp[i - 1][j - m - 1];
                } else {
                    way -= Math.pow(m + 1, i - 1);
                }
                dp[i][j] = way;
            }
        }
        return (double) dp[k][n] / Math.pow(m + 1, k);
    }

    public static void main(String[] args) {
        System.out.println(killMonster1(8, 3, 7));     // 0.841796875
        System.out.println(killMonster2(8, 3, 7));     // 0.841796875
        System.out.println(killMonster3(8, 3, 7));     // 0.841796875
    }
}
